//https://leetcode.cn/problems/maximum-rows-covered-by-columns/?envType=daily-question&envId=2024-01-04



class Solution {
    int ans=0;
    void dfs(vector<int>& vt,int m,int n,int idx,int numSelect,int curstate){
        if(idx>=n){
            if(__builtin_popcount(curstate)==numSelect){
                int cnt=0;
                for(int i=0;i<m;++i){
                    if((vt[i]^(vt[i]&curstate))==0) ++cnt;
                }
                ans=max(ans,cnt);
            }
            return ;
        }
        dfs(vt,m,n,idx+1,numSelect,curstate);
        dfs(vt,m,n,idx+1,numSelect,curstate|(1<<idx));
    }
public:
    int maximumRows(vector<vector<int>>& matrix, int numSelect) {
        int m=matrix.size();
        int n=matrix[0].size();
        vector<int> vt(m);
        for(int i=0;i<m;++i){
            int cur=0;
            for(int j=0;j<n;++j){
                if(matrix[i][j]) cur|=(1<<j);
            }
            vt[i]=cur;
        }
        dfs(vt,m,n,0,numSelect,0);
        return ans;
    }
};